package 华为OD机试真题2023.进阶题;

import utils.MyUtil;

import java.io.File;
import java.io.FileNotFoundException;
import java.util.ArrayDeque;
import java.util.Scanner;

public class HJ33_计算网络信号 {
    public static void main(String[] args) throws FileNotFoundException {
        Scanner in = new Scanner(new File("src/main/java/华为OD机试真题2023/进阶题/input/33.txt"));
        MyUtil.START();
        Solution(in);
        //        Solution2(in);
        //        Solution3(in);
        MyUtil.END();
    }

    static int row = 0;
    static int column = 0;
    static int[][] matrix, visited;
    static int posX = 0, posY = 0;

    static void Solution(Scanner in) {
        row = in.nextInt();
        column = in.nextInt();
        in.nextLine(); // 吸收回车
        matrix = new int[row][column];
        visited = new int[row][column];
        String[] sArray = in.nextLine().split(" ");
        int dfsX = 0, dfsY = 0, signal = 0, k = 0;
        for (int i = 0; i < row; i++) {
            for (int j = 0; j < column; j++) {
                matrix[i][j] = Integer.parseInt(sArray[k++]);
                if (matrix[i][j] > 0) {
                    dfsX = i;
                    dfsY = j;
                    signal = matrix[i][j];
                }
            }
        }
        dfs(dfsX, dfsY, signal);
        posX = in.nextInt();
        posY = in.nextInt();
        System.out.println(matrix[posX][posY]);
    }

    static void dfs(int x, int y, int signal) {
        if (x < 0 || x >= row || y < 0 || y >= column || signal <= 0 || matrix[x][y] == -1) {
            return;
        }
        if (signal > matrix[x][y]) { // 注意：这一步至关重要，否则可能会错误
            visited[x][y] = 0;
        }
        if (visited[x][y] == 1) {
            return;
        }
        visited[x][y] = 1;
        matrix[x][y] = Math.max(signal, matrix[x][y]);
        dfs(x - 1, y, signal - 1); // 上
        dfs(x + 1, y, signal - 1); // 下
        dfs(x, y - 1, signal - 1); // 左
        dfs(x, y + 1, signal - 1); // 右
    }

    static void Solution2(Scanner sc) {
        ArrayDeque<int[]> sites = new ArrayDeque<>();
        String[] strs = sc.nextLine().split(" ");
        int m = Integer.parseInt(strs[0]);
        int n = Integer.parseInt(strs[1]);
        int[][] nums = new int[m][n];
        int start = 0;
        String[] s = sc.nextLine().split(" ");
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                int num = Integer.parseInt(s[start++]);
                nums[i][j] = num;
                if (num > 0) {
                    sites.addLast(new int[] {i, j, num});
                }
            }
        }
        String[] strslast = sc.nextLine().split(" ");
        int x = Integer.parseInt(strslast[0]);
        int y = Integer.parseInt(strslast[1]);

        boolean[][] isused = new boolean[m][n];
        int[][] df = new int[][] {{0, 1}, {0, -1}, {1, 0}, {-1, 0}};
        while (!sites.isEmpty()) {
            int[] ints = sites.pollFirst();
            int sitex = ints[0];
            int sitey = ints[1];
            int sitevalue = ints[2];
            isused[sitex][sitey] = true;
            if (sitevalue > 1) {
                for (int i = 0; i < 4; i++) {
                    int newx = sitex + df[i][0];
                    int newy = sitey + df[i][1];
                    if (newx >= 0
                            && newx < m
                            && newy >= 0
                            && newy < n
                            && !isused[newx][newy]
                            && nums[newx][newy] != -1) {
                        isused[newx][newy] = true;
                        nums[newx][newy] = sitevalue - 1;
                        sites.add(new int[] {newx, newy, sitevalue - 1});
                    }
                }
            }
        }

        System.out.println(nums[x][y]);
    }

    public static int i;
    public static int j;
    public static int[][] signals; // 网格地图二维数组
    public static int signalX; // 信号源横坐标
    public static int signalY; // 信号源纵坐标

    static void Solution3(Scanner sc) {
        int m = sc.nextInt();
        int n = sc.nextInt();
        signals = new int[m][n];
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                signals[i][j] = sc.nextInt();
                if (signals[i][j] != 0 && signals[i][j] != -1) { // 信号
                    signalX = i;
                    signalY = j;
                }
            }
        }
        i = sc.nextInt();
        j = sc.nextInt();
        handle(signalX, signalY, signals[signalX][signalY]);
        System.out.println(signals[i][j]);
    }

    /**
     * @param x 网格地图横坐标
     * @param y 网格地图纵坐标
     * @param signal 信号值
     */
    public static void handle(int x, int y, int signal) {
        if (x == i && y == j) { // 达到所求位置
            return;
        }
        if (signal == 0 || signal == -1) { // 无信号进行传播
            return;
        }
        if (x < i) {
            if (signals[x + 1][y] != -1) { // 下一个位置如果是阻隔则无需进行操作
                signals[x + 1][y] = Math.max(signals[x + 1][y], signal - 1);
            }
            handle(x + 1, y, signals[x + 1][y]);
        }
        if (y < j) {
            if (signals[x][y + 1] != -1) { // 下一个位置如果是阻隔则无需进行操作
                signals[x][y + 1] = Math.max(signals[x][y + 1], signal - 1);
            }
            handle(x, y + 1, signals[x][y + 1]);
        }
        if (x > i) {
            if (signals[x - 1][y] != -1) { // 下一个位置如果是阻隔则无需进行操作
                signals[x - 1][y] = Math.max(signals[x - 1][y], signal - 1);
            }
            handle(x - 1, y, signals[x - 1][y]);
        }
        if (y > j) {
            if (signals[x][y - 1] != -1) { // 下一个位置如果是阻隔则无需进行操作
                signals[x][y - 1] = Math.max(signals[x][y - 1], signal - 1);
            }
            handle(x, y - 1, signals[x][y - 1]);
        }
    }
}
